\documentclass[12pt,a4paper]{article}

\usepackage[OT4]{polski}
\usepackage[english,polish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{a4wide}
%\usepackage[left=2.5cm,top=3cm,right=2.5cm, bottom=3cm]{geometry}
\usepackage{indentfirst}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{pdfpages}

%opening
\title{}
\author{Tomasz Werszko}


\begin{document}

\thispagestyle{empty}
\noindent
\begin{minipage}[c]{0.4\columnwidth}
	Rafał Magda, 148794\\
	Tomasz Werszko, 149195
\end{minipage}
\begin{minipage}[c]{0.6\columnwidth}
	\hfill Wrocław, dn.\ \today\\
\end{minipage}
\hfill
\vspace{2cm}
\begin{center}
	\begin{Large}
		\emph{Implementacja, testy i ocena algorytmu syntezy układów cyfrowych wykorzystujących urządzenia NDR}\\
  	\end{Large}
\end{center}

\begin{center}
	Projekt z przedmiotu \textit{Kodowanie i szyfrowanie danych}\\
\end{center}


\begin{center}
	Rok akad. 2008/2009, kierunek: INF IBS
\end{center}
\vspace{0.2ex}
\begin{flushright}
	\begin{minipage}[t]{0.4\columnwidth}
	\noindent
		PROWADZĄCY:\\
		dr inż. Maciej Nikodem
	\end{minipage}
\end{flushright}
\vfill
\tableofcontents
\newpage

\section{Cel projektu}

Celem projektu jest implementacja algorytmu syntezy funkcji boolowskich
na układy GTG (\textit{generalised treshold gate}) skonstruowane z urządzeń
o ujemnej rezystancji dynamicznej (NDR).

\section{Implementacja}
Program realizowany w ramach projektu napisany został w języku \textit{JAVA} w środowisku \textit{Eclipse}. W naszym kodzie wykorzystujemy również klasy 
z pakietu \textit{BExpred} (The Boolean Expression Reducer \cite{bexpred}), które po odpowiednim zaadaptowaniu do potrzeb naszego projektu zajmują się 
przetwarzaniem wyrażenia logicznego w postaci ciągu znaków do postaci drzewa, obliczaniem wartości wyrażeń dla zadanych wektorów wejściowych, wyznaczaniem 
tabel prawdy i redukcją wyrażeń. Ponieważ nasz program jest obsługiwany przez użytkownia z poziomu terminala, korzystamy z biblioteki \textit{JSAP} 
(The Java Simple Argument Parser \cite{jsap}), , która umozliwia podawanie argumentów do programu w sposób zgodny ze standardem \textit{POSIX}

Po wprowadzeniu wyrażenia logicznego do programu, napisane przez nas klasy zajmują się jego przetworzeniem. Wyrażenie jest parsowane i (jeśli jest poprawne)
jest przekształcane do postaci Reed'a-Muller'a wykorzystując metdę trójkąta opisaną na stronie \cite{trojkat}. Następnie szereg klas (\textit{RM, GTGExpression, 
GTGXor, GTGOr, GTGAnd}) dostarcza metody rozbijające wyrażenie do postaci ułatwiającej jego dalsze przetwarzanie algorytmem syntezy. Klasa \textit{GTGExpression}
przechowuje wyrażenie w postaci listy kolejnych argumentów \textit{xor} (klasa GTGXor), z których każdy jest listą argumentów \textit{or} (klasa \textit{GTGOr}), które z kolei
są listą argumentów \textit{and} (klasa \textit{GTGAnd}).

Klasa \textit{GTGExpression} dostarcza metodę \textit{synthesize()}, która przeprowadza syntezę GTG w oparciu o algorytm opisany w artykule 
\textit{,,Boolean Logic Function Synthesis for Generalised Threshold Gate Circuits''}\cite{article}.

Użytkownik otrzymuje wynik w postaci szeregu wyrażeń opisujących gałęzie układu GTG oraz informację o relacji pomiędzy $NDR_{l}$ i $NDR_{d}$.
W celu kontroli poprawności generowana jest tabela prawdy wyniku, która porównywana jest z tabelą prawdy wyrażenia wejściowego. 
Wynik porównania jest przedstawiany użytkownikowi.

\section{Obsługa programu}
Program posiada wiele opcji uruchamiania. Ich pełną listę można uzyskać uruchamiając program z parametrem \textit{-h} lub \textit{--help}. Została ona również
zamieszczona poniżej:
\newpage
\begin{scriptsize}
\begin{verbatim}
Usage: java -jar gtg.jar
       [-r|--reed-muller] [-s|--sum-of-products] [-p|--product-of-sums] 
       [-z|--synthesis] [-t|--truth-table] [-h|--help] [-v|--verbose] 
       [-c|--time] [-i|--iterations] [-b|--branches] 
       [-a|--algorithm] (-e|--expression) <expression> 
       [--tests tests1,tests2,...,testsN ]

  [-r|--reed-muller]
        Prints the expresson in Reed-Muller form.
  [-s|--sum-of-products]
        If the expression is reducable prints reduced expression as a sum of
        products.
  [-p|--product-of-sums]
        If the expression is reducable prints reduced expression as a product of
        sums.
  [-z|--synthesis]
        Synthesizes GTG circuit.
  [-t|--truth-table]
        Prints truth table of the expression.
  [-h|--help]
        Prints help.
  [-v|--verbose]
        Prints more information about generation process.
  [-c|--time]
        Prints sysnthesis algorithm time.
  [-i|--iterations]
        Prints number of synthesis algorithm iterations.
  [-b|--branches]
        Prints number of branches needed to realize GTG circuit.
  [-a|--algorithm]
        Prints GTG expression synthesis algorithm.
  (-e|--expression) <expression>
        Operation priorities are (from the highest to the lowest): NOT ( ~ )
        AND ( * )
        OR ( + ) , XOR ( ^ ) - the same priority (only order matters)
        You can use brackets - () to change priorities
        You MUST add quotation mark - " at the beginning and at the end of the
        expression.
        (default: )
  [--tests tests1,tests2,...,testsN ]
        Makes automatic tests. Requires 3 intiger parameters:
        numer of tests,
        number of variables,
        0 - for R-M expressions, 1 - for normal expressions.
        Generates output in .csv format.
        No other parameters are considered, except --verbose to print progress
        in error output.
        Example: --tests 100,5,0

Authors: Rafal Magda (rafalmag@gmail.com)
         Tomasz Werszko (twerszko@gmail.com)


\end{verbatim}
\end{scriptsize}

\section{Testowanie}
Aby sprawdzić działanie programu przeprowadziliśmy szereg testów, których wyniki zostały zamieszczone w dalszej części rozdziału. Testowanie wymagało zaimplementowania
generatora wyrażeń testowych. Opracowaliśmy do tego celu prosty algorytm, którego pseudokod znajduje się poniżej.
\begin{algorithm}
\label{alg:generator}
\floatname{algorithm}{Algorytm}
\caption{Algorytm losowania wyrażeń testowych}
\begin{algorithmic}[1]
\REQUIRE n: liczba zmiennych
\STATE Wylosuj zmienną z listy z przedziału 1..n
\IF{każda ze zmiennych została wylosowana przynajmniej raz i co najmniej jedna zmienna wystąpiła przynajmniej n razy}
\STATE Zakończ generowanie
\ELSE
\STATE Wylosuj znak ,,\texttt{*}'' lub ,,\texttt{\^{ }}''
\ENDIF
\STATE \textbf{goto:} 1
\end{algorithmic}
\end{algorithm}

Wykorzystując algorytm 1 oraz opisaną wcześniej opcję \textit{- -tests} przeprowadziliśmy pomiary czasu poszczególnych etapów
syntezy. Ponieważ dla dużej liczby testów wylosowane wyrażenia mogły się powtarzać, przypadki takie zostały na koniec ręcznie wyeliminowane. Ostateczną
liczbę wyrażeń testowych pokazuje tabela \ref{tab:liczba-testow}.
\begin{figure}[h!]
\begin{center}
	\begin{tabular}{|l||c|c|c|c|c|c|c|c|c|}
	\hline
	liczba zmiennych & 2 &	3 &	4 &	5 &	6 &	7 &	8 &	9 &	10 \\ \hline
	liczba wyrażeń testowych &	4 &	97 &	584 &	901 &	97 &	99 &	99 &	100 &	93 \\ \hline
	\end{tabular}
\end{center}
\caption{Liczba wyrażeń testowych w zależności od liczby zmiennych}
\label{tab:liczba-testow}
\end{figure}

Wyniki testów zostały przedstawione na poniższych wykresach.

\newpage
%\includepdf[nup=1x2, landscape, pages=1-5]{results.pdf}
%\includepdf[nup=1x2, landscape, pages=4-7]{dummy.pdf}
\includepdf[nup=1x2, pages=1-5, trim=0 20mm 0 20mm, clip, scale=.85, pagecommand={}]{results.pdf}

\section{Wnioski}
Głównym celem projektu było empiryczne sprawdzenie czy algorytm syntezy GTG jest prawidłowy. Wszystkie przeprowadzone testy zakończyły się oczekiwanym wynikiem.
Porównywaliśmy tabelę prawdy wyrażenia podawanego na wejście z tabelą prawdy wyrażenia uzyskanego w procesie syntezy. We wszystkich sprawdzonych przypadkach
tabele te były równoważne.

Wyniki testów pokazały, że wszystkie badane zależności czasowe mają charakter wykładniczy i rosną bardzo szybko wraz ze wzrostem liczby zmiennych.
Przeprowadzenie większej liczby prób dla wyrażeń o liczbie zmiennych wiekszej niż 10 okazało się niemożliwe w rozsądnym czasie. Być może należałoby 
zrewidować zaimplementowane w programie metody przetwarzania wyrażeń i zmniejszyć ilość obliczeń poprzez ich uproszczenie. Algorytm pracował na wirtualnej 
maszynie \textit{JAVA'y}, co miało również istotny wpływ na szybkość obliczeń.
\addcontentsline{toc}{section}{Literatura}
\begin{thebibliography}{Literatura}
	\bibitem{article}
	,,Boolean Logic Function Synthesis for Generalised Threshold Gate Circuits''.
	\bibitem{bexpred}
	The Boolean Expression Reducer [w:]\\* {\small{\texttt{http://sourceforge.net/projects/bexpred}}}. 
	\bibitem{jsap}
	JSAP: the Java Simple Argument Parser [w:]\\* {\small{\texttt{http://martiansoftware.com/jsap}}}.
	\bibitem{trojkat}
	Minimalizacja wielomianem Reed's-Muller'a [w:]\\* {\small{\texttt{http://wuwuwu.com.pl/tc/sch6.htm\#trojkat}}}.
\end{thebibliography}
\end{document}

